Last substring in lexicographical order

Time: O(N); Space: O(N); hard

Given a string s, return the last substring of s in lexicographical order.

Example 1:

Input: s = “abab”

Output: “bab”

Explanation:

  • The substrings are [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”].

  • The lexicographically maximum substring is “bab”.

Example 2:

Input: s = “leetcode”

Output: “tcode”

Notes:

  • 1 <= len(s) <= 4 * 10^5

  • s contains only lowercase English letters.

Hints:

  1. Assume that the answer is a sub-string from index i to j. If you add the character at index j+1 you get a better answer.

  2. The answer is always a suffix of the given string.

  3. Since the limits are high, we need an efficient data structure.

  4. Use suffix array.

[3]:

import collections

class Solution1(object):
    """
    Time:  O(n)
    Space: O(n)
    """
    def lastSubstring(self, s):
        """
        :type s: str
        :rtype: str
        """
        count = collections.defaultdict(list)
        for i in range(len(s)):
            count[s[i]].append(i)

        max_c = max(count.keys())
        starts = {}
        for i in count[max_c]:
            starts[i] = i+1

        while len(starts)-1 > 0:
            lookup = set()
            next_count = collections.defaultdict(list)
            for start, end in starts.items():
                if end == len(s):  # finished
                    lookup.add(start)
                    continue
                next_count[s[end]].append(start)
                if end in starts:  # overlapped
                    lookup.add(end)
            next_starts = {}
            max_c = max(next_count.keys())
            for start in next_count[max_c]:
                if start not in lookup:
                    next_starts[start] = starts[start] + 1
            starts = next_starts

        return s[list(map(int, starts.keys()))[0]:]

[4]:

sol = Solution1()
s = "abab"
assert sol.lastSubstring(s) == "bab"
s = "leetcode"
assert sol.lastSubstring(s) == "tcode"

[5]:

class Solution2(object):
    def lastSubstring(self, s):
        """
        :type s: str
        :rtype: str
        """
        chars = set(s)
        if len(chars) == 1:
            return s
        start = sorted(chars, reverse=True)[0]
        possibles = []
        for i, c in enumerate(s):
            if c == start:
                possibles.append([i, i])
        while len(possibles) > 1:
            cs = []
            tmp = []
            for i, j in possibles:
                if j + 1 >= len(s):
                    continue
                cs.append(s[j + 1])
            m = max(cs)
            for i, j in possibles:
                if j + 1 >= len(s):
                    continue
                if s[j + 1] == m:
                    tmp.append([i, j + 1])
            possibles = tmp
        return s[possibles[0][0]:]

[6]:

sol = Solution2()
s = "abab"
assert sol.lastSubstring(s) == "bab"
s = "leetcode"
assert sol.lastSubstring(s) == "tcode"